This invention generally relates to techniques and systems for accessing objects in computers and, more particularly, to techniques and systems which efficiently arbitrate concurrent access to objects in multithreaded or multitasking computer systems.
The evolution of the computer industry is unparalleled in its rate of growth and complexity. Personal computers, for example, which began as little more than feeble calculators with limited memory, tape-driven input and monochrome displays, are now able to tackle almost any data processing task. While this meteoric increase in power was sufficient to satisfy the demands of most application programmers and end users, the corresponding increase in complexity associated with computers created an ease-of-use problem which the industry was somewhat slower in solving. Thus, designers were faced with a new challenge: to harness this computing power in a form usable by even those with relatively little computer training to smooth the transition of other industries into a computer-based information paradigm.
As a result, in the early to mid-1980's, many new I/O philosophies, such as "user friendly", "WYSIWYG" and "menu driven" came to the forefront of the industry. These concepts are particularly applicable to microcomputers, also known as personal computers, which are intended to appeal to a broad audience of computer users, including those who previously feared and mistrusted computers. An important aspect of computers which employs these concepts was, and continues to be, the interface which allows the user to input commands and data and receive results, which is commonly referred to as a graphical user interface (GUI).
One type of GUI is based on a visual metaphor which uses a monitor screen as a work surface called a "desktop" where documents are presented in relocatable regions termed "windows". The user interacts with the computer by, for example, moving objects on the desktop, choosing commands from menus and manipulating window controls, such as checkboxes and scrollbars. These objects may include, for example, files and folders which are iconically represented on the desktop and whose contents are stored by a file management system. An exemplary desktop screen is reproduced as FIG. 1.
The success of this type of interface is evident from the number of companies which have emulated the desktop environment. Even successful concepts, however, must continually be improved upon to keep pace with the rapid growth in this industry. For example, the advent of multimedia, especially CD-ROM devices, has provided vast quantities of secondary storage which have been used to provide video capabilities, e.g., live animation and video clips, as regular components of application displays. As these new capabilities are developed, the GUIs and underlying operating system software are modified or rewritten to take advantage thereof.
In the last few years, personal computers have been evolving towards multitasking, i.e., the capability to run several applications concurrently. Initial steps toward true multitasking included the capability to display several applications at once, i.e., in different windows, albeit only one application was active at a time, and to allow the user to easily switch between the windowed applications. In true multitasking environments, each application is associated with one or more threads which independently coordinate the processing for that application. This leads to the possibility that two or more threads may attempt to operate on a file system object, e.g., a file or a folder, at the same time. In certain situations, e.g. when one thread is altering data while another is reading the same data, concurrent access to file system objects is problematic.
For example, consider the hierarchical arrangement of file system objects illustrated in FIG. 2. Therein, a tree is illustrated with a root folder A having two child folders B and C, each containing a pair of files D and E and F and G, respectively. Suppose that a user wants to copy folder A to a new folder A' as illustrated and, while the copying process is ongoing, attempts to modify the contents of file E. The question then arises as to whether this latter operation should be permitted and, if so, will the contents of the copy A' include the original file E or the modified version of file E.
These types of concurrent access problems for file systems have been addressed in conventional multitasking systems. According to one solution, which has implemented as part of the WINDOWS 95 operating system, access to an object and its children is completely restricted while an operation involving the object is in progress. Thus, in the context of the example of FIG. 2, the user would not be permitted to modify (or even view) any of the objects A-G while folder A was being copied to create folder A'. However, this solution has the drawback that it may severely limit a user's access to many objects (for example if a very large copy operation is being performed), which frustrates the objectives behind multitasking. Moreover, such a complete access restriction is unwarranted for certain combinations of activities, e.g., viewing an object while copying that object or moving an object while copying that object, which can be performed in parallel.
Another solution to concurrent access of file system objects is to simply provide no access restrictions. This solution is found, for example, in the NeXT operating system and provides the user with the freedom to perform plural operations on the same object at the same time. However, completely unrestricted access to the same objects also creates certain problems. Consider again the example of FIG. 2 with unrestricted access. If the user modifies file E before that file has been copied to folder A', then folder A and folder A' will be identical at the end of the copy operation. If, however, the user modifies file E after file E has been copied then the contents of folder A and folder A' will be different. This is just one example of the uncertainty of results which manifests itself as a result of completely unrestricted multithreaded access to file system objects.
Accordingly, it would be desirable to provide techniques and systems for managing file system objects in a multithreaded enviromnent in which multiple threads can simultaneously operate on the same object whenever possible to maximize throughput and availability of objects to a user, but without causing object incoherency and inconsistent file operation results.